package com.xq.algorithm.sort;

import static com.xq.algorithm.AlgorithmTest.printlnAry;

/**
 * @author jltxseo
 *         Created by junlintianxia on 2017/07/09.
 */

public class InsertSortAlgorithm {

    /**
     * 普通直接插入排序算法
     * 比较一个后移一个；
     * @param a
     *         空间复杂度O(1) 　 　　 　　
     *         平均时间复杂度O(n^2)
     *
     *         将一个数据插入到已经排好序的有序数据中，
     *         从而得到一个新的、个数加一的有序数据，
     *         算法适用于少量数据的排序，是稳定的排序方法。
     *         64 5 7 89 6 24
     *         5 64 7 89 6 24
     *         5 7 64 89 6 24
     *         5 7 64 89 6 24
     *         5 6 7 64 89 24
     *         5 6 7 24 64 89
     */
    public static void insertSort(int[] a){
        if(a == null)return;
        int i,j,temp;
        for (i=1; i < a.length; i++){
            temp = a[i];
            j = i;
            while (j > 0 && a[j-1] >= temp){  //大于temp的有序数往后移
                a[j] = a[j - 1];
                j--;
            }
            a[j] = temp;
            printlnAry(a);
        }
    }

    public static void testInsertSort(){
        int[] a = {64,5,7,89,6,24};
        printlnAry(a);
        insertSort(a);
        printlnAry(a);
    }



    /**
     *  折半插入排序
     *  先找到位置，然后一起移动；
     * @param a
     * ,使用使用折半查找的方式寻找插入点的位置, 可以减少比较的次数,但移动的次数不变,
     * 时间复杂度和空间复杂度和直接插入排序一样，在元素较多的情况下能提高查找性能。
     */
    public static void binaryInsertSort(int[] a){
        //从数组的第二个位置开始遍历值
        for (int i= 1; i < a.length; i++){
            int temp = a[i];//暂存要插入的值
            int pre = 0; //有序序列开始和结尾下标申明
            int last = i-1;
            // 折半查找出插入位置 a[pre]
            while(pre <= last){
                int mid = (pre + last) / 2;
                if(temp < a[mid]){
                    last = mid - 1;
                }else {
                    pre = mid + 1;
                }
            }
            //a[i]已经取出来存放在key中，把下标从pre + 1到 i-1的元素依次后移
            for(int j= i; j >= pre + 1; j--){
                a[j] = a[j - 1];
            }

            a[pre] = temp;
            printlnAry(a);
        }
    }

    public static void testBinaryInsertSort(){
        int[] a = {64,5,7,89,6,24};
        printlnAry(a);
        binaryInsertSort(a);
        printlnAry(a);
    }

    /**
     * 希尔排序
     * 一个不稳定的排序，其时间复杂度受**步长（增量）**的影响
     * 　　空间复杂度：　Ｏ(1)
     *     时间复杂度：　平均 O(n^1.3) 　　　最好　O(n) 　　最坏　O(n^2)
     * @param a
     */
    public static void  shellSort(int[] a){
        if(a == null)return;
        int i,j,temp,h=1;
        int n = a.length;
        //确定初始步长
        while(h < n / 3){
            h = h * 3;
        }

        while (h > 0){
            for (i = h; i < n; i++){
                temp = a[i];
                j = i;
                while(j > h - 1 && a[j-h] >= temp){
                    a[j] = a[j - h];
                    j = j - h;
                }
                a[j] = temp;
            }
            printlnAry(a);
            h = h / 3;
        }
    }


    public static void testshellSort(){
        int[] a = {64,5,7,89,6,24};
        printlnAry(a);
        shellSort(a);
        printlnAry(a);
    }

}
